package bst;

import java.util.NoSuchElementException;

/**
 * 普通二叉搜索树
 */
public class BSTree {
    private class TreeNode{
        int val ;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    private int size;
    private TreeNode root;

    public void add(int val){
        root = add(root , val);
    }

    /**
     * 以root为根树插入一个新节点返回树根
     * @param root
     * @param val
     * @return
     */
    private TreeNode add(TreeNode root, int val) {
        if (root == null){
            TreeNode curNode = new TreeNode(val);
            size++;
            return curNode;
        }else {
            if (val < root.val){
                root.left = add(root.left , val);
            }
            if (val > root.val){
                root.right = add(root.right , val);
            }
        }
        return root;
    }

    public boolean contains(int val){
        return contains(root , val);
    }

    private boolean contains(TreeNode root, int val) {
        if (root == null){
            return false;
        }
        if (root.val == val){
            return true;
        }else if (val < root.val){
            return contains(root.left , val);
        }else {
            return contains(root.right , val);
        }

    }

    public int findMin(){
        if (size == 0){
            throw new NoSuchElementException("BST 是空的");
        }
        TreeNode minNode = minNode(root);
        return minNode.val;
    }

    //当遇到第一个左子树为空时，此时的root节点就是最小的
    private TreeNode minNode(TreeNode root) {
        if (root.left == null){
            return root;
        }
        return minNode(root.left);
    }

    public int findMax(){
        if (size == 0){
            throw  new NoSuchElementException("BST 是空的");
        }
        TreeNode maxNode = maxNode(root);
        return maxNode.val;
    }

    private TreeNode maxNode(TreeNode root) {
        if (root.right == null){
            return root;
        }
        return maxNode(root.right);
    }

    //删除BST最小值节点，并且返回删除节点的值
    public int removeMin(){
        int min = findMin();
        root = removeMin(root);//删除以root为根的最小值节点返回树根
        return min;

    }

    //删除以root为根的最小值节点返回树根
    private TreeNode removeMin(TreeNode root) {
        //注意方法语义，删除当前树的最小值节点，并且返回删除后的树根
        if (root.left == null){
            TreeNode right = root.right;
            root.right = root = null;//root.right = null是断开连线上一行已经暂存了root.right
            //root = null是断开最小值连线，也就是删除这样才有回收机制处理
            size --;
            return right;
        }
        root.left = removeMin(root.left);//也就是这里，获得最后一个删除的右子树（空不空不影响）而这里的root是处理节点的上一级
        //所以root.left直接就连起来了
        return root;
    }

    public int removeMax(){
        int max = findMax();
        root = removeMax(root);
        return max;
    }

    private TreeNode removeMax(TreeNode root) {
        if (root.right == null){
            TreeNode left = root.left;
            root.right = root = null;
            size -- ;//注意处理树的大小
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    public void remove(int val){
        //删除root根树的任意节点
        root = remove(root , val);
    }

    //删除root根节点val值节点返回树根，返回树根
    private TreeNode remove(TreeNode root, int val) {
        if (root == null){
            throw new NoSuchElementException("BST 是空的没有这个值");
        }else if (val < root.val){
            root.left = remove(root.left , val);
            return root;
        }else if (val > root.val){
            root.right = remove(root.right , val);
            return root;
        }else {
            if (root.left == null){
                TreeNode right = root.right;
                root.right = root =  null;
                size -- ;
                return right;
            }
            if (root.right == null){
                TreeNode left = root.left;
                root.left = root = null;
                size -- ;
                return left;
            }
            TreeNode successor = maxNode(root.left);//看这里，找的是啥
            successor.left = removeMax(root.left);//连接递归到上一层就会连上了，只需要处理好这一层的关系，把删掉左边最大值的树连到前驱
            successor.right = root.right;
            //此时successor已经处理完了，只需要把多余的东西删掉交给jvm回收处理,也就是原来这颗树的及他的左右孩子
            root.left = root.right = root = null;
            return successor;
        }
    }


    public String toString(){
        StringBuffer strBuffer  = new StringBuffer();
        generateBStreeStr(root , 0 ,strBuffer);
        return strBuffer.toString();
    }

    /**
     * 先序遍历以root根的树，将根存在strBuffer
     * @param root
     * @param height
     * @param strBuffer
     */
    private void generateBStreeStr(TreeNode root, int height, StringBuffer strBuffer) {
        if (root == null){
            strBuffer.append(generateHeightStr(height)).append("NULL\n");
            return;
        }
        strBuffer.append(generateHeightStr(height)).append(root.val).append("\n");
        generateBStreeStr(root.left , height + 1 , strBuffer);
        generateBStreeStr(root.right , height + 1 , strBuffer);

    }

    /**
     * 根据当前树的层次打印
     * @param height
     * @return
     */
    private  String generateHeightStr(int height){
        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < height; i++) {
            stringBuffer.append("--");
        }
        return stringBuffer.toString();
    }

}
